package fun.coding.leetcode;

import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

public class MergeKSortedLists {

	public static void main(String[] args) {

	}
	// TODO: This uses extra space, another way to solve this is keep merging 2 lists together. 
	public ListNode mergeKLists(List<ListNode> lists) {
		if (lists == null || lists.size() == 0) return null;
		
		ListNode dummy = new ListNode(-1);
		ListNode cur = dummy;
		
		ListComparator c = new ListComparator();
		Queue<ListNode> heap = new PriorityQueue<ListNode>(lists.size(), c);
		
		int size = lists.size();
		
		for (int i = 0; i < size; i++) {
			if (lists.get(i) != null) {
				heap.add(lists.get(i)); // Don't forget PQ doesn't allow to add null
			}
		}
		while (!heap.isEmpty()) {
			ListNode t = heap.poll();
			cur.next = t;
			if (t.next != null) {
				heap.add(t.next);
			}
			cur = t;
		}
	
		return dummy.next;
	}
	
	public class ListComparator implements Comparator<ListNode> {
		@Override
		public int compare(ListNode o1, ListNode o2) {
			if (o1.val > o2.val) return 1; // reverse those will result in a max heap
			if (o1.val < o2.val) return -1;
			return 0;
		}
	}

}
